from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 构建邻接表
        graph = [[] for _ in range(numCourses)]
        # 填充邻接表
        for pre in prerequisites:
            a, b = pre
            graph[b].append(a)

        # 标记 0 表示未访问，1 表示正在访问，2 表示已经访问
        visited = [0] * numCourses

        def dfs(node):
            # 正在遍历，存在环
            if visited[node] == 1:
                return False
            # 遍历到一个遍历完的节点，不存在环
            if visited[node] == 2:
                return True
            # 当前节点 正在遍历
            visited[node] = 1
            # 遍历它的邻接节点
            for i in graph[node]:
                if not dfs(i):  # 存在环
                    return False
            # 当前节点遍历完
            visited[node] = 2
            return True

        # 遍历每一个节点
        for i in range(numCourses):
            # 如果存在环
            if not dfs(i):
                return False
        return True